/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package gamaze;

import genetic_algorithm.GA;
import java.util.ArrayList;
import java.util.Iterator;

/**
 * This class supports the generic functions of a genetic algorithm.
 * @author pborrego
 */
public class GAMaze extends GA {
    public GAMaze(Maze m)
    {
        this.pop = new ArrayList<String>();
        this.mutationRate = .1f;
        this.popSize = 20;
        this.m = m;
    }

    public String crossover(String dad, String mom)
    {
        int pos;
        String[] dadsegs, momsegs;

        pos = (int)(Math.random() * (dad.length() - 1));
        dadsegs = new String[3];
        dadsegs[0] = dad.substring(0, pos);
        dadsegs[1] = dad.substring(pos);

        dad = dadsegs[1];
        pos = (int)(Math.random() * (dad.length()));
        dadsegs[1] = dad.substring(0, pos);
        dadsegs[2] = dad.substring(pos);

        pos = (int)(Math.random() * (mom.length() - 1));
        momsegs = new String[3];
        momsegs[0] = mom.substring(0, pos);
        momsegs[1] = mom.substring(pos);

        mom = momsegs[1];
        pos = (int)(Math.random() * (mom.length()));
        momsegs[1] = mom.substring(0, pos);
        momsegs[2] = mom.substring(pos);

        return dadsegs[0] + momsegs[1] + dadsegs[2];
    }

    public String mutate(String dna)
    {
        int directions[] = {Maze.E, Maze.N, Maze.S, Maze.W};

        if(Math.random() > this.getMutationRate())
        {
            return dna;
        }

        int pos = (int)(Math.random() * dna.length());

        // find type...insertion, deletion or flip
        switch((int)(Math.random() * 3))
        {
            case GA.DELETE:
                dna = dna.substring(0,pos) + dna.substring(pos+1, dna.length());
                break;
            case GA.FLIP:
                dna = dna.substring(0,pos) +
                        Integer.toString(
                            directions[(int)(Math.random() * directions.length)]) +
                        dna.substring(pos+1, dna.length());
                break;
            case GA.INSERT:
                dna = dna.substring(0,pos) +
                        Integer.toString(
                            directions[(int)(Math.random() * directions.length)]) +
                        dna.substring(pos, dna.length());
                break;
        }

        return dna;
    }

    /**
     * Evaluates the raw fitness value of the dna string
     *
     * @param dna - a maze direction path
     * @return the lenght of the path
     */
    public float fitness(String dna)
    {
        return dna.length();
    }
    
    /**
     * Evaluates the fitness of each dna in the population. The results
     * are stored in rawFit array.
     * @param rawFit
     */
    public void evalFit(ArrayList<Float> rawFit)
    {
        for(int i=0; i<this.popSize; i++)
        {
            rawFit.add(new Float(this.fitness(pop.get(i))));
        }
    }

    /**
     * Populates the pop variable with random complete maze paths.
     */
    @Override
    public void populate()
    {
        int directions[] = {Maze.E, Maze.N, Maze.S, Maze.W};
        String directionNames[] = {Integer.toString(Maze.E), Integer.toString(Maze.N), Integer.toString(Maze.S), Integer.toString(Maze.W)};
        int d = 0;
        String dna = "";
        int maxDNA = m.getHeight() * m.getWidth();

        System.out.println("Populating...");
        for(int i=0; i<getPopSize(); i++)
        {
            m.reset();
            dna = "";
            while(!m.finished())
            {
                d = (int)(Math.random() * directions.length);

                if(m.move(directions[d]))
                {
                    dna += directionNames[d];
                }

                if(dna.length() > maxDNA) {
                    // our path is getting too long start over.
                    m.reset();
                    dna = "";
                }
            }
            pop.add(dna);
            System.out.println("DNA " + i);
        }
    }

    /**
     * @return the popSize
     */
    public int getPopSize() {
        return popSize;
    }

    /**
     * @param popSize the popSize to set
     */
    public void setPopSize(int popSize) {
        this.popSize = popSize;
    }

    /**
     * Normalizes all the raw fitness values around the shortest path.
     *
     * @return a set of normalized (0-1) values corresponding to each of the
     * dna strings in the population.
     */
    protected ArrayList<Float> normalize()
    {
        ArrayList<Float> fitnessVals = new ArrayList<Float>();
        ArrayList<Float> normalFit = new ArrayList<Float>();
        int sumInverseFitness = 0;

        evalFit(fitnessVals);
        for(int j=0; j<this.popSize; j++)
        {
            sumInverseFitness += (int)(1 / fitnessVals.get(j));
        }

        for(int j=0; j<this.popSize; j++)
        {
            normalFit.add((1 / fitnessVals.get(j)) / sumInverseFitness);
        }

        return normalFit;
    }

    protected String selectDNA(ArrayList<Float> normalFit)
    {
        double probablity = Math.random();
        double curProb = 0;
        int i = -1;

        while(probablity > curProb)
        {
            i++;
            curProb += normalFit.get(i);
        }

        return this.pop.get(i);
    }

    public String bestDNA()
    {
        int best = 0;

        for(int i=0; i<this.popSize; i++)
        {
            if(this.fitness(this.pop.get(i)) < this.fitness(this.pop.get(best)))
            {
                best = i;
            }
        }

        return this.pop.get(best);
    }

    @Override
    public void run(int generations)
    {
        ArrayList<Float> normalFitnessVals;
        String dad, mom, child;
        ArrayList<String> newPop = new ArrayList<String>();

        for(int i=0; i < generations; i++)
        {
            System.out.println("Current generation: " + i);
            for(int j=0; j<this.popSize; j++)
            {
                do
                {
                    normalFitnessVals = this.normalize();
                    dad = this.selectDNA(normalFitnessVals);
                    mom = this.selectDNA(normalFitnessVals);

                    child = this.crossover(dad, mom);
                    child = this.mutate(child);
                } while(!m.validPath(child));
                newPop.add(child);
            }

            Iterator<String> newPopIt = newPop.iterator();
            this.pop.clear();
            while(newPopIt.hasNext())
            {
                this.pop.add(newPopIt.next());
            }
            newPop.clear();
        }
    }

    protected ArrayList<String> pop;
    protected Maze m;
    private int popSize;
}
